using System.Collections.Generic;
using System;
    
namespace Mono.Boost.Graph
{


    public class ConnectedComponents
    {

        public static void strongly_connected_components<GraphType, ComponentType>(GraphType g, ComponentType component)
            where GraphType : IGraph
            where ComponentType : IDictionary<uint,uint>
        {

            Queue<uint> przetworzone = new Queue<uint>();     //FIXME

            foreach (uint v in g.vertices)
                if (!component.ContainsKey(v))
                {
                    component.Add(v, ~0U);
                    Stack<uint> vals = new Stack<uint>();
                    Stack<IEnumerator<EdgeInfo>> its = new Stack<IEnumerator<EdgeInfo>>();

                    uint now = v;
                    IEnumerator<EdgeInfo> nit = g.outgoing(now).GetEnumerator();
                    while (true)
                    {
                        if (nit.MoveNext())
                        {
                            if (!component.ContainsKey(nit.Current.v))
                            {
                                its.Push(nit);
                                vals.Push(now);
                                now = nit.Current.v;
                                nit = g.outgoing(now).GetEnumerator();
                                component.Add(now, ~0U);
                            }
                        }
                        else
                        {
                            przetworzone.Enqueue(now);
                            if (vals.Count == 0)
                                break;
                            else
                            {
                                nit = its.Pop();
                                now = vals.Pop();
                            }
                        }
                    }
                }

            uint nc = 0;
            Queue<uint> q = new Queue<uint>();
            while (przetworzone.Count != 0)
            {
                uint now = przetworzone.Dequeue();
                if (component[now] == ~0U)
                {
                    q.Enqueue(now);
                    component[now] = nc;
                    while (q.Count != 0)
                    {
                        now = q.Dequeue();
                        foreach (EdgeInfo ei in g.outgoing(now))
                            if (component[ei.v] == ~0U)
                            {
                                component[ei.v] = nc;
                                q.Enqueue(ei.v);
                            }
                    }
                    nc += 1;
                }
            }
        }
    }
}

